// 最小栈
// 实现一个栈，带有pop出栈，push 入栈，getMin 方法
// O(n) => O(1)  空间换时间   i
// push  i  指针 最小值
// 缺点
// 1. 栈  熟悉  []  push pop
// 2. ADT getMin 方法 O(n)
// 3. 指针变量 i  最小值  出栈 i
// 4. 空间换时间  双栈
// 用栈来实现队列

var MinStack = function() {
    this.stack = []; // 栈
    this.minStack = []; // 辅助栈 入栈的是最小值，最小值在最上面
}
// 把常考算法作为手写题来处理
MinStack.prototype.push = function(x) {
    if (this.minStack.length && x < this.getMin()) {
        this.minStack.push(x);
    }
    this.stack.push(x);
}
MinStack.prototype.pop = function() {
    let x = this.stack.pop();
    if (x == this.getMin()) {
        this.minStack.pop();
    }
}
MinStack.prototype.getMin = function() {
    if (!this.minStack.length) {
        throw new Error('stack is empty')
    }
    return this.minStack[this.minStack.length - 1] // O(1)
}
